
import random
import time
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation

# 生成500个随机数
random_numbers = [random.randint(1, 10000) for _ in range(500)]

# 用列表和元组分别存储
list_data = list(random_numbers)
tuple_data = tuple(random_numbers)

# 快速排序实现，并记录每一步状态
def quick_sort(arr):
    steps = []
    arr_copy = arr.copy()  # 创建原数组的副本，避免修改原始数据
    
    def partition(arr, low, high):
        pivot = arr[high]
        i = low - 1
        for j in range(low, high):
            if arr[j] <= pivot:
                i += 1
                arr[i], arr[j] = arr[j], arr[i]
                steps.append(arr.copy())  # 记录每次交换后的数组状态
        arr[i + 1], arr[high] = arr[high], arr[i + 1]
        steps.append(arr.copy())  # 记录分区后的数组状态
        return i + 1
    
    def _quick_sort(arr, low, high):
        if low < high:
            pi = partition(arr, low, high)
            _quick_sort(arr, low, pi - 1)
            _quick_sort(arr, pi + 1, high)
    
    _quick_sort(arr_copy, 0, len(arr_copy) - 1)
    return steps

# 冒泡排序实现，并记录每一步状态
def bubble_sort(arr):
    steps = []
    n = len(arr)
    for i in range(n):
        for j in range(0, n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
            steps.append(arr.copy())
    return steps

def measure_time(data, sort_func, container_type):
    start_time = time.time()
    if container_type == 'list':
        sorted_steps = sort_func(list(data))
    else:
        sorted_steps = sort_func(list(data))  # 元组需要先转为列表
    end_time = time.time()
    return end_time - start_time, sorted_steps

# 测量各种情况下的排序时间
times = {}
sorted_steps_dict = {}
list_quick_time, list_quick_steps = measure_time(list_data, quick_sort, 'list')
list_bubble_time, list_bubble_steps = measure_time(list_data, bubble_sort, 'list')
tuple_quick_time, tuple_quick_steps = measure_time(tuple_data, quick_sort, 'tuple')
tuple_bubble_time, tuple_bubble_steps = measure_time(tuple_data, bubble_sort, 'tuple')

times = {
    'list_quick': list_quick_time,
    'list_bubble': list_bubble_time,
    'tuple_quick': tuple_quick_time,
    'tuple_bubble': tuple_bubble_time
}
sorted_steps_dict = {
    'list_quick': list_quick_steps,
    'list_bubble': list_bubble_steps,
    'tuple_quick': tuple_quick_steps,
    'tuple_bubble': tuple_bubble_steps
}

# 输出结果
print("排序耗时比较：")
for key, value in times.items():
    container, algorithm = key.split('_')
    print(f"{container.capitalize()} + {algorithm.capitalize()} Sort: {value:.6f} seconds")

# 可视化结果
labels = ['List + Quick', 'List + Bubble', 'Tuple + Quick', 'Tuple + Bubble']
values = [times['list_quick'], times['list_bubble'], times['tuple_quick'], times['tuple_bubble']]

plt.figure(figsize=(10, 8))
plt.bar(labels, values, color=['skyblue', 'lightcoral', 'lightgreen', 'orange'])
plt.title('Sorting Time Comparison')
plt.xlabel('Container + Sort')
plt.ylabel('Time(s)')
plt.xticks(rotation=45)
plt.tight_layout()
plt.show()

# 排序过程可视化函数
def visualize_sorting(steps, title):
    fig, ax = plt.subplots()
    bar_rects = ax.bar(range(len(steps[0])), steps[0], align="edge")
    ax.set_xlim(0, len(steps[0]))
    ax.set_ylim(0, max(steps[0]))
    ax.set_title(title)

    def update(frame):
        for rect, val in zip(bar_rects, steps[frame]):
            rect.set_height(val)
        return bar_rects

    ani = FuncAnimation(fig, update, frames=len(steps), interval=50, repeat=False)
    plt.show()

# 可视化排序过程
visualize_sorting(list_quick_steps, 'List + Quick Sort')
visualize_sorting(list_bubble_steps, 'List + Bubble Sort')
visualize_sorting(tuple_quick_steps, 'Tuple + Quick Sort')
visualize_sorting(tuple_bubble_steps, 'Tuple + Bubble Sort')